package DP;

/**
 * @author 曹见朋
 * @create 2024-06-12-20:18
 */
public class Main01Bag {

    public static int bag(int[] weights, int[] values, int bag){

        int m = weights.length;
        int[][] dp = new int[m][bag + 1];

        for(int i = 0; i < m; i++){
            dp[i][0] = 0;
        }

        for(int j = 0; j <= bag; j++){
            if(j >= weights[0]){
                dp[0][j] = values[0];
            }
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j <= bag; j++){
                if(j >= weights[i]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j <= bag; j++){
                System.out.print(" " + dp[i][j]);
                if(j == bag){
                    System.out.println();
                }
            }
        }

        return dp[m - 1][bag];

    }

    public static void main(String[] args){
        int[] weight = new int[]{1, 3, 4};
        int[] values = new int[]{15, 20, 30};
        int bag = 4;

        int result = bag(weight, values, bag);
        System.out.println();
        System.out.println(result);
    }
}
